/* I know STL supplies this functionality but in order to garentee stability 
 * across multiple platforms this simple stack was created.
 * The class only maintain node memroy.  The user supplyed memory is never 
 * touched.  The use of a pool will increse efficenty.
 *
 *  Created by Garrett williams on 5/19/05.
 *  Copyright 2005 Drag'N Flies. All rights reserved.
 */

#ifndef SIMPLEstack
#define SIMPLEstack

template<class TYPE>
struct SimpleStackNode
{
    TYPE data;
    SimpleStackNode *next;
};

template<class TYPE>
class SimpleStack
{
  public:
    SimpleStack();
    SimpleStack(int size);
    ~SimpleStack();
    void clear();     // empty the stack put memory in pool.
    void push(TYPE ); // push a node onto the stack.
    bool  pop(TYPE&); // pop the next node off the stack.
  private:
    SimpleStackNode<TYPE> *stack; // the stack.
    SimpleStackNode<TYPE> *pool;  // pool of free node for putting on the stack.
    SimpleStackNode<TYPE> *stack_front;
    SimpleStackNode<TYPE> *stack_back;
    SimpleStackNode<TYPE> *pool_front;

    SimpleStackNode<TYPE> * get(); // get the pointer to a free node.
    // put node back when finished.
    void store(SimpleStackNode<TYPE> *store_node);
};

template<class TYPE>
SimpleStack<TYPE>::SimpleStack()
{
    stack = 0;
    pool  = 0;
    stack_front = 0;
    stack_back  = 0;
    pool_front  = 0;
}

// inital size of pool.
template<class TYPE>
SimpleStack<TYPE>::SimpleStack(int size)
{
    stack = 0;
    pool  = 0;
    stack_front = 0;
    stack_back  = 0;
    pool_front  = 0;

    SimpleStackNode<TYPE> *added = 0;
    for (int i=0;i<size;i++)
    {
        added = new SimpleStackNode<TYPE>;
        added->next = pool_front;
        pool_front = added;
    }
}

template<class TYPE>
SimpleStack<TYPE>::~SimpleStack()
{
    SimpleStackNode<TYPE> *del_node;
    while(pool_front)
    {
        del_node = pool_front;
        pool_front = pool_front->next;
        delete del_node;
    }
    while(stack_front)
    {
        del_node = stack_front;
        stack_front = stack_front->next;
        delete del_node;
    }
}


template<class TYPE>
void SimpleStack<TYPE>::clear()
{
    while(stack_front)
    {
        SimpleStackNode<TYPE> *del_node;
        del_node = stack_front;
        stack_front = stack_front->next;
        store(del_node);
    }
    stack_back = 0;
}

template<class TYPE>
void SimpleStack<TYPE>::push(TYPE in_data)
{
    if(stack_front)
    {
        // stack_back is a temp varable
        stack_back = get();
        stack_back->next = stack_front;
        stack_front = stack_back;
    }
    else
    {
        stack_front = get();
        stack_front->next = 0;
    }
    stack_front->data = in_data;
}

template<class TYPE>
bool  SimpleStack<TYPE>::pop(TYPE &rt_data)
{
    bool rt = true;
    SimpleStackNode<TYPE> *store_node;
    if(stack_front) 
    {
        // remove front node.
        store_node = stack_front;
        // send stored data back.
        rt_data = stack_front->data;
        // goto next in stack.
        stack_front = stack_front->next;
        // store node in pool.
        store(store_node);
    }
    else
    {
        rt = false;
        stack_back = 0;
    }
    return rt;
}

template<class TYPE>
SimpleStackNode<TYPE> * SimpleStack<TYPE>::get()
{
    SimpleStackNode<TYPE> *rtnode = pool_front;
    if(pool_front) pool_front = pool_front->next;
    else rtnode = new SimpleStackNode<TYPE>;
    return rtnode;
}

template<class TYPE>
void SimpleStack<TYPE>::store(SimpleStackNode<TYPE> *store_node)
{
    store_node->data = (TYPE)0;
    store_node->next = pool_front;
    pool_front = store_node;
}

#endif
